数据结构 Tree 二叉树的前中后序遍历

前置工具准备

准备一个 TreeNode

static class TreeNode {
    int value;
    TreeNode right;
    TreeNode left;

    TreeNode(int val) {
        value = val;
    }
}

生成完全二叉树的工具

/**
 * 生成一颗完全二叉树
 */
public static TreeNode generateTree(int len, int max) {
    int[] arr = new int[len - 1];
    for (int i = 0; i < arr.length; i++) {
        arr[i] = (int) (Math.random() * max);
    }
    return buildTree(null, arr, 0);
}

/**
 * 构建树
 */
private static TreeNode buildTree(TreeNode root, int[] nums, int index) {
    if (index >= nums.length) {
        return null;
    }
    root = new TreeNode(nums[index]);
    root.left = buildTree(root.left, nums, 2 * index + 1);
    root.right = buildTree(root.right, nums, 2 * index + 2);
    return root;
}

打印树到控制台

编写一个打印二叉树到控制台的方法，方便观察

/**
 * 打印树到控制台
 */
public static void printBinaryTree(TreeNode root) {
    printBinaryTree(root, 0);
}

public static void printBinaryTree(TreeNode root, int level) {
    if (root == null)
        return;
    printBinaryTree(root.right, level + 1);
    if (level != 0) {
        for (int i = 0; i < level - 1; i++)
            System.out.print("|\t\t");
        System.out.println("|-------" + root.value);
    } else
        System.out.println(root.value);
    printBinaryTree(root.left, level + 1);
}

使用测试：

public static void main(String[] args) {
    TreeNode root = generateTree(12, 100);
    printBinaryTree(root);
}

output：

|       |-------45
|-------87
|       |-------96
56
|       |       |-------50
|       |-------23
|       |       |-------89
|-------87
|       |       |-------19
|       |-------18
|       |       |-------28

遍历二叉树的递归序 ⭐

看左神的视频 0:55:00 （左神，yyds !!!）

递归函数在执行一次，会回到自己 3 次

public static void f(TreeNode head) {
    if (head == null) return;
    // 1
    f(head.left);
    // 2
    f(head.right);
    // 3
}

如下：

            
    3      
5    6   7

可以看到每个节点都经过这三次：

2 4 4 4 2 5 5 5 2 1 3 6 6 6 3 7 7 7 3 1

下面的具体算法代码也是根据这里来的

先序的递归序

就是在第一次递归序的时候打印，其它两次不打印

如下：

      1              
  2      3      
4  5    6   7

每次只执行第一次

1 2 4 4 4 2 5 5 5 2 1 3 6 6 6 3 7 7 7 3 1
^ ^ ^       ^         ^ ^       ^

所以最后打印顺序是：
1 2 4 5 3 6 7

所以它打印时只需在 1 位置处打印

public static void f(TreeNode head) {
    if (head == null) return;
    // 1
    System.out.println(head.value);
    f(head.left);
    // 2
    f(head.right);
    // 3
}

中序的递归序

就是在第二次递归序的时候打印，其它两次不打印

如下：

      1              
  2      3      
4  5    6   7

每次只执行第二次

1 2 4 4 4 2 5 5 5 2 1 3 6 6 6 3 7 7 7 3 1
      ^   ^   ^     ^     ^   ^   ^

所以最后打印顺序是：
4 2 5 1 6 3 7

所以它打印时只需在 2 位置处打印

public static void f(TreeNode head) {
    if (head == null) return;
    // 1
    f(head.left);
    // 2
    System.out.println(head.value);
    f(head.right);
    // 3
}

后续的递归序

就是在第三次递归序的时候打印，其它两次不打印

如下：

      1              
  2      3      
4  5    6   7

每次只执行第三次

1 2 4 4 4 2 5 5 5 2 1 3 6 6 6 3 7 7 7 3 1
        ^       ^ ^         ^       ^ ^ ^

所以最后打印顺序是：
4 5 2 6 7 3 1

所以它打印时只需在 3 位置处打印

public static void f(TreeNode head) {
    if (head == null) return;
    // 1
    f(head.left);
    // 2
    f(head.right);
    // 3
    System.out.println(head.value);
}

如何判别哪种遍历？⭐

前序遍历：先输出父节点，再遍历左子树和右子树。中序遍历：先遍历左子树，再输出父节点，最后遍历右子树后序遍历：先遍历左子树，再遍历右子树，最后输出父节点

所以判断前中后序只需看输出父节点的顺序

二叉树的先序遍历

前序遍历：根结点 ---> 左子树 ---> 右子树

使用递归的方法

Java 的写法

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
}

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    traversal(root,list);
    return  list;
}

public void traversal(TreeNode node, List<Integer> arr) {
    if (node == null) {
        return;
    }
    arr.add(node.val);
    traversal(node.left,arr);
    traversal(node.right,arr);
}

JavaScript 的写法

/**
 * 前序遍历，递归版本
 */

class TreeNode {
  constructor(val, left, right) {
    this.val = val === undefined ? 0 : val
    this.left = left === undefined ? null : left
    this.right = right === undefined ? null : right
  }
}

/**
 * 注意，输入的这个 root 已经内置了数据结构了，无需自己去维护
 * 
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function (root) {
  const answer = []
  // 递归
  const traversal = (node, arr) => {
    if (!node) return
    arr.push(node.val)
    // 先递归左边
    traversal(node.left, arr)
    // 再递归左边
    traversal(node.right, arr)
  }

  traversal(root, answer)
  return answer
}

迭代的方法 ⭐

其实就是通过栈来手动模拟递归的过程

看左神的视频 1:09:00

public static void f(TreeNode head) {
    if (head == null) return;
    // 1
    f(head.left);
    // 2
    f(head.right);
    // 3
}

1、从栈中弹出一个节点 2、打印（处理）节点 3、先右再左入栈（如果有） 4、重复上面的步骤

public static List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    if (root == null) {
        return list;
    }

    // 先让头节点入栈（相当于第一次调用）
    stack.push(root);
    //  应该将其看成上面那个递归那样的关系
    while (!stack.isEmpty()) {
        TreeNode temp = stack.pop(); // 弹出栈，模拟正在调用方法
        list.add(temp.val);
        // 这里先 Right 再 Left 是因为先执行的是 left 节点的方法，再执行的 right 方法
        if (temp.right != null) {
            stack.push(temp.right);
        }
        if (temp.left != null) {
            stack.push(temp.left);
        }
    }
    return list;
}

迭代的方法：修改指针法 ⛔

这种方法了解就好

public static void main(String[] args) {
    TreeNode root = new TreeNode(1,
            new TreeNode(2,new TreeNode(4),new TreeNode(5)), new TreeNode(3));
    System.out.println(preorderTraversal(root));
}

public static List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    if (root == null) {
        return list;
    }

    while (!stack.isEmpty() || root != null) {
        while (root != null) {
            list.add(root.val);
            stack.push(root);
            root = root.left;
        }
        TreeNode temp = stack.pop();
        root = temp.right;
    }

    return list;
}

通过修改指针的方式来遍历

二叉树的中序遍历

中序遍历：左子树---> 根结点 ---> 右子树

使用递归的方法

只需更改一个顺序就行了

public static void main(String[] args) {
    TreeNode root = new TreeNode(1,
            new TreeNode(2), new TreeNode(3,
            null, new TreeNode(4)));
    System.out.println(inorderTraversal(root));
}

public static List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    traversal(root,list);
    return list;
}

public static void traversal(TreeNode node, List<Integer> arr) {
    if (node == null) {
        return;
    }
    traversal(node.left,arr);
    arr.add(node.val);
    traversal(node.right,arr);
}

迭代的方法

参考左神的视频 1:22:00

先让树的全部左边界进栈，依次弹出的过程中打印，对弹出节点的右树执行一样的操作

    public static List<Integer> inorderTraversal(TreeNode head) {
        List<Integer> result = new ArrayList<>();
        if (head == null) return result;
        Stack<TreeNode> stack = new Stack<>();
        // 复用 head 指针
        while (!stack.isEmpty() || head != null) {
            // 不停的左边界进栈
            if (head != null) {
                stack.push(head);
                head = head.left;
            } else {
                head = stack.pop();
                result.add(head.value); 
                head = head.right;
            }
        }
        return result;
    }

迭代的方法：修改指针法 ⭐

这种方法了解就好

public static void main(String[] args) {
    TreeNode root = new TreeNode(1,
            new TreeNode(2,new TreeNode(4),new TreeNode(5)), new TreeNode(3));
    System.out.println(inorderTraversal(root));
}

public static List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    if (root == null) {
        return list;
    }

    while (!stack.isEmpty() || root != null) {
        // 取得最左边的那个节点
        while (root != null) {
            stack.push(root);
            root = root.left;
        }

        TreeNode temp = stack.pop();
        list.add(temp.val);
        root = temp.right;
    }

    return list;
}

二叉树的后序遍历

后序遍历，最后一个元素必为根

后序遍历：左子树 ---> 右子树 ---> 根结点

使用递归的方法

只需更改一个顺序就行了

public static void main(String[] args) {
    TreeNode root = new TreeNode(1,
            new TreeNode(2), new TreeNode(3,
            null, new TreeNode(4)));
    System.out.println(postorderTraversal(root));
}

public static List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    traversal(root,list);
    return list;
}

public static void traversal(TreeNode node, List<Integer> arr) {
    if (node == null) {
        return;
    }
    traversal(node.left,arr);
    traversal(node.right,arr);
    arr.add(node.val);
}

使用迭代的方法 ⭐

参考左神的视频 1:16:40 后序的迭代其实就是前序的倒序，即创建一个收集栈，像前序那样遍历树（但是这里是先左后右），但一般并不执行，而是把结果放在一个收集栈里面，再次遍历收集栈，这个收集栈就是逆序的结果了

    public static List<Integer> postorderTraversal(TreeNode head) {
        List<Integer> result = new ArrayList<>();
        if (head == null) return result;

        Stack<TreeNode> stack = new Stack<>();
        Stack<TreeNode> resultStack = new Stack<>();

        stack.push(head);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            resultStack.push(node);
            // 注意：这里是先左后右
            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right);
        }

        while (!resultStack.isEmpty()) {
            result.add(resultStack.pop().value);
        }
        return result;
    }

之所以这里是先左后右是因为在递归的时候这个打印 value 的操作就是在右节点执行完后才执行的，所以这里将其颠倒过来（使用迭代模拟递归入栈顺序与执行顺序是反的）

如下：

public static void f(TreeNode head) {
    if (head == null) return;
    // 1
    f(head.left);
    // 2
    f(head.right);
    // 3
    System.out.println(head.value);
}

从中序与后序遍历序列构造二叉树

注：从前序与中序遍历序列构造二叉树和这个类似，这里就直接跳过了

根据一棵树的中序遍历与后序遍历构造二叉树。（假设树中没有重复的元素）

如下输入：

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树：

解题思路后序遍历，最后一个元素必为根，所以只要找到最后一个元素在中序遍历中的位置就可以将数组一分为二，左侧为左子树的遍历结果，右侧为右子树

对拆分后的两个数组递归的进行上述操作即可

public TreeNode buildTree(int[] inorder, int[] postorder) {
    int len = inorder.length;
    if (len == 0)
        return null;
    // 别忘了下标 -1
    return dfs(inorder, postorder, 0, len - 1, 0, len - 1);
}

/**
 * 
 * @param inorder   中序数组
 * @param postorder 后续数组
 * @param head1     中序数组头下标
 * @param tail1     中序数组尾下标
 * @param head2     后续数组头下标
 * @param tail2     后续数组尾下标
 * @return
 */
TreeNode dfs(int[] inorder, int[] postorder, int head1, int tail1, int head2, int tail2) {
    // 健壮性判断，当头下标大于尾下标时返回 null
    if (tail2 < head2)
        return null;

    int val = postorder[tail2]; // 取后序数组最后一个 val 为 root
    TreeNode root = new TreeNode(val);

    if (tail2 == head2)
        return root; // 如果当前头尾下标相等了，表示遍历完成了

    int mid = 0; // 创建一个临时变量来存储中间下标

        // 遍历中序数组，找到 root 的位置
    while (inorder[head1 + mid] != val) {
        mid++;
    }

    // 前序数组不用取中间的那个位置（所以 left 和 right 的 head1 + mid 用 +1 -1 规避了）
    root.left = dfs(inorder, postorder, 
    head1, 
    head1 + mid - 1, 
    head2, 
    head2 + mid - 1);
    // 同上后续数组尾下标不需要取最后一个，所以尾部要 -1

    root.right = dfs(inorder, postorder, 
    head1 + mid + 1, 
    tail1, 
    head2 + mid, 
    tail2 - 1);

    return root;
}

前序和中序构造二叉树

type TreeNode struct {
    Left *TreeNode
    Right *TreeNode
    Val int
}

func dfs(xianxu []int, zhongxu []int) *TreeNode {
    if len(xianxu) == 0 {
        return nil
    }
    
    root := xianxu[0]
    var index int
    for idx, v := range zhongxu {
        if v == root {
            index = idx
            break
        }
    }

    return &TreeNode{
        Val: root,
        Left: dfs(xianxu[1:index+1], zhongxu[:index]),
        Right: dfs(xianxu[index+1:], zhongxu[index+1:]),
    }
}

前置工具准备​

准备一个 TreeNode​

生成完全二叉树的工具​

打印树到控制台​

遍历二叉树的递归序 ⭐​

先序的递归序​

中序的递归序​

后续的递归序​

如何判别哪种遍历？⭐​

二叉树的先序遍历​

使用递归的方法​

迭代的方法 ⭐​

迭代的方法：修改指针法 ⛔​

二叉树的中序遍历​

使用递归的方法​

迭代的方法​

迭代的方法：修改指针法 ⭐​

二叉树的后序遍历​

使用递归的方法​

使用迭代的方法 ⭐​

从中序与后序遍历序列构造二叉树​

前序和中序构造二叉树​

前置工具准备

准备一个 TreeNode

生成完全二叉树的工具

打印树到控制台

遍历二叉树的递归序 ⭐

先序的递归序

中序的递归序

后续的递归序

如何判别哪种遍历？⭐

二叉树的先序遍历

使用递归的方法

迭代的方法 ⭐

迭代的方法：修改指针法 ⛔

二叉树的中序遍历

使用递归的方法

迭代的方法

迭代的方法：修改指针法 ⭐

二叉树的后序遍历

使用递归的方法

使用迭代的方法 ⭐

从中序与后序遍历序列构造二叉树

前序和中序构造二叉树